package com.itheima.leetcode;

/**
 * 删除链表的倒数第 N 个结点
 *
 * @FileName E03LeetCode19
 * @Description
 * @Author Sword
 * @date 2025-03-19
 **/
public class E03LeetCode19 {

    /*//方法一 递归
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode s = new ListNode(-1, head);
        recursion(s, n);
        return s.next;
    }

    //递归查找元素的倒数位置
    private static int recursion(ListNode p, int n) {
        if (p == null) {
            return 0;
        }

        int nth = recursion(p.next, n);     //下一个节点的倒数位置
        System.out.println(p.val + " " + nth);

        if (nth == n) {
            //删除节点
            p.next = p.next.next;
        }
        return nth + 1;
    }*/


    //方法二
    //s -> 1 -> 2 -> 3 -> 4 -> 5 -> null
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode s = new ListNode(-1, head);
        ListNode p1 = s;
        ListNode p2 = s;

        for (int i = 0; i < n + 1; i++) {
            p2 = p2.next;
        }

        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        p1.next = p1.next.next;

        return s.next;
    }

    public static void main(String[] args) {
        ListNode listNode = ListNode.of(1, 2, 3, 4, 5);
        System.out.println(listNode);
        ListNode removeNthFromEnd = E03LeetCode19.removeNthFromEnd(listNode, 5);
        System.out.println(removeNthFromEnd);
    }
}
